package 力扣日常刷题.木23一月.第20天320;

public class Demo103寻找两个正序数组的中位数 {


    public double findMedianSortedArrays(int[] nums1,int[] nums2) {
        int length1 = nums1.length,length2 = nums2.length;
        int totalLength = length1 + length2;
        if(totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1,nums2,midIndex + 1);
            return median;
        } else {
           int midIndex = totalLength / 2 - 1,midIndex2 = totalLength / 2;
           double median = (getKthElement(nums1,nums2,midIndex+1) + getKthElement(nums1,nums2,midIndex2+1))/2.0;
           return median;
        }
    }

    public int getKthElement(int[]num1,int[]num2,int k) {
        int length1 = num1.length,length2 = num2.length;
        int index1 = 0,index2 = 0;

        while(true) {
            //边界条件
            if(index1 == length1) {
                return num2[index2 + k - 1];
            }
            if(index2 == length2) {
                return num1[index1 + k - 1];
            }
            if(k == 1) {
                return Math.min(num1[index1],num2[index2]);
            }

            //sample
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half,length1) - 1;
            int newIndex2 = Math.min(index2+half,length2) - 1;
            int pivot1 = num1[newIndex1],pivot2 = num2[newIndex2];
            if(pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            }else{
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}
